//给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 13
//输出：6
// 
//
// 示例 2： 
//
// 
//输入：n = 0
//输出：0
// 
//
// 
//
// 提示： 
//
// 
// 0 <= n <= 2 * 109 
// 
// Related Topics 递归 数学 动态规划 
// 👍 304 👎 0

package leetcode.editor.cn;

//Java：数字 1 的个数
public class NumberOfDigitOne_233 {
    public static void main(String[] args) {
        Solution solution = new NumberOfDigitOne_233().new Solution();
        // TO TEST
        System.out.println(solution.countDigitOne(100));
    }

    /**
     * 9 1
     * 99 20
     * 999 300
     * 2999  2 * 300 + 1000 + 300
     * 101   1 * 20 + 1
     */
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int countDigitOne(int n) {
            int count = 0;
            String k = n + "";
            int len = k.length() - 1;
            for (int i = len; i >= 0; i--) {
                int t = Integer.parseInt(k.substring(i, i + 1));
                int m = len - i;
                int tn = new Double(Math.pow(10, m - 1)).intValue() * m * t;
                if (t == 1 && i < len) {
                    tn += Integer.parseInt(k.substring(i + 1)) + 1;
                } else if (t >= 1) {
                    tn += Math.pow(10, m);
                }
                count += tn;
            }
            return count;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}